#!/usr/bin/python
# -*- coding: utf-8 -*-

import sys
import exceptions
import random

colors = {'red'                : "\033[31m",
          'green'              : "\033[32m",
          'blue'               : "\033[34m",
          'purple'             : "\033[35m",
          'cyan'               : "\033[36m",
          'default'            : "\033[0m"  }

def cc(msg, color):
    if colors.has_key(color):
        return colors[color] + msg + colors['default']
    else:
        return msg

mesaj = {"x":"[x] Oyuncu kazandı !.","o":"[o] Bilgisayar kazandı !.","0":"[-] Berabere !."}

def kesmeyakala(exception, value, tb):
    """Control+C çalışsın ;)"""
    if exception == exceptions.KeyboardInterrupt:
        print(cc("\n\nKlavye kesmesi.. çıkılıyor..","red"))
        sys.exit()

def hepsiesit(list):
    """Hücrelerin hepsi aynı ise True döndürür"""
    return reduce(lambda x, y: x and y, (x == list[0] for x in list), True)

class tablo:
    """Tabloyu oluşturan class"""
    def __init__(self,hs,zeka=0):
        """Tablonun boş halini yarat"""
        self._hs = hs
        self.hs = hs*hs
        self.hucreler = [' ']*self.hs
        self.kazananlar = self.kazananlari_hesapla()
        self.zeka=zeka
        self.sayac=0.0

    def kazananlari_hesapla(self):
        """Belirlenen hücre sayisi için kazanan hücreleri belirler"""
        ret =[]
        satir =[]
        c=[x for x in range(self.hs)]
        a=self._hs
        j=0
        for i in range(a):
            ret.append(c[j:a+j])                #yatay kazananlar
            ret.append(range(i,a*(a-1)+1+i,a))  #dikey kazananlar
            j+=a
        ret.append(range(0,a*a,a+1))            #diagonal sol üstten sağ alta
        ret.append(range(a-1,a*(a-1)+1,a-1))    #diagonal sağ üstten sol alta
        return ret

    def kazanan(self):
        """Kazananı belirle"""
        for i in self.kazananlar:
            if self.hucreler[i[0]] != ' ' and hepsiesit([self.hucreler[j] for j in i]):
                return self.hucreler[i[0]]

    def biter(self):
        """Oyun ne durumda"""
        return self.kazanan() or not self.boshucreler()

    def boshucreler(self):
        """Bos hucreleri geri dondur"""
        boslar=[]
        for pos in range(self.hs):
            if self.hucreler[pos]==' ':
                boslar.append(pos)
        return boslar

    def yazdir(self):
        """Tabloyu ekrana bas"""
        print "\n","-"*self._hs*3
        j=0
        aa=[]
        for i in range(self._hs):
            aa.append(self.hucreler[j:j+self._hs])
            j+=self._hs

        for satir in aa:
            print '  '.join(satir)
        print "-"*self._hs*3,"\n"

    def hamleyap(self,hamle,oyuncu):
        """Gönderilen oyuncu(bilg.,insan) için istenilen hamleyi gerçekleştir"""
        self.hucreler[hamle]=oyuncu

    def hamleyigerial(self,hamle):
        """Gönderilen hamleyi geri alır"""
        self.hucreler[hamle]=' '

def oyuncu_hamle(tablo):
    """Oyuncudan hamlesini iste kontrolu yap ve gerçekleştir"""
    if not tablo.biter():
        tablo.yazdir()
        print cc("Boş hücreler ","green"),tablo.boshucreler()
        hamle = input(cc("Hamle yapacağınız hücreyi seçin : ","purple"))
        if hamle in tablo.boshucreler():
            tablo.hamleyap(hamle,'x')
        else:
            print cc("Bu hücreye hamle yapamazsınız!!","red")
            oyuncu_hamle(tablo)

def bilgisayar_hamle(tablo):
    """Bilgisayar en iyi sonucu bul ve oyna"""
    if not tablo.biter():
        x='x'
        o='o'
        oyuncular = { x : o, o : x }
        oyuncu = o

        def fact(n):
            import math
            if not n >= 0:
                raise ValueError("n must be >= 0")
            if math.floor(n) != n:
                raise ValueError("n must be exact integer")
            if n+1 == n:  # catch a value like 1e300
                raise OverflowError("n too large")
            result = 1
            factor = 2
            while factor <= n:
                result *= factor
                factor += 1
            return result

        def durumhesapla(toplam,sayac):
            return (float(sayac)*100)/float(toplam)

        def hamlehesapla(hamle, p=oyuncu,hamlesayisi=0):
            try:
                tablo.hamleyap(hamle, p)
                tablo.sayac+=1
                out = sys.stdout
                msg= "\rSu an %f tamamlanmis durumda." % durumhesapla(hamlesayisi,tablo.sayac)
                out.write(msg)
                out.flush()
                if tablo.biter():
                    return durum(tablo.kazanan())
                tumhamleler = (hamlehesapla(sonrakihamle, oyuncular[p],hamlesayisi=hamlesayisi) for sonrakihamle in tablo.boshucreler())
                if p == oyuncu:
                    min_element = 1
                    for n in tumhamleler:
                        if n == -1:
                            return n
                        min_element = min(n,min_element)
                    return min_element
                else:
                    max_element = -1
                    for n in tumhamleler:
                        if n == +1:
                            return n
                        max_element = max(n,max_element)
                    return max_element
            finally:
                tablo.hamleyigerial(hamle)

        def _hamle():
            """Bilgisayarın hamlesini hesaplar"""
            bos=[]

            #ilk hamle ise random
            if len(tablo.boshucreler())==tablo.hs:
                print cc("Algoritma : RASTGELE","cyan")
                return rastgele()

            #tekhamle kontrolü
            for j in ['o','x']:
                for i in tablo.boshucreler():
                    tablo.hamleyap(i,j)
                    if tablo.kazanan()==j:
                        print cc("Algoritma : TEKHAMLE","cyan")
                        return i
                    tablo.hamleyigerial(i)

            #minimax
            _hamlesayisi = fact(len(tablo.boshucreler()))
            tablo.sayac=0.0
            print cc("Algoritma : MİNİMAX","cyan")
            hamleler = [(hamle, hamlehesapla(hamle,hamlesayisi=_hamlesayisi)) for hamle in tablo.boshucreler()]
            random.shuffle(hamleler)
            hamleler.sort(key = lambda (hamle, kazanan): kazanan)
            return hamleler[-1][0]

            #son çare rastgele
            print cc("Algoritma : RASTGELE","cyan")
            return rastgele(tablo.boshucreler())

        def rastgele(liste=0):
            if liste:
                random.shuffle(liste)
                return liste[0]
            return random.randint(0,tablo.hs-1)

        def durum(kazanan):
            if kazanan == oyuncu:
                return +1
            if kazanan == None:
                return 0
            return -1

        i = _hamle()
        print cc("Bilgisayar hamle yaptı : %d"%i,"purple")
        tablo.hamleyap(i,'o')

if __name__=="__main__":
    sys.excepthook=kesmeyakala
    hs=0
    while hs<3:
        hs = input(cc("Kaç hücre taban alınsın ? 3x3 için 3, En az 3(üç) olmalı ! : ","cyan"))

    ilk=0
    tt=tablo(hs)
    while ilk not in [1,2]:
        ilk = input(cc("İlk kim oynayacak ? [1:Bilgisayar, 2:Oyuncu] :: ","green"))
    for i in range(tt.hs):
        if ilk==2:
            oyuncu_hamle(tt)
            bilgisayar_hamle(tt)
        else:
            bilgisayar_hamle(tt)
            oyuncu_hamle(tt)

    tt.yazdir()
    if tt.kazanan():
        print cc(mesaj["%s"%tt.kazanan()],"green")
    else:
        print cc(mesaj["0"],"green")

